package sort;

/**
 * 直接插入排序
 *
 * @param <T>
 * @author zj
 */
public class InsertSort<T extends Comparable<T>> implements Sort<T> {

    @Override
    public void sort(T[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        for (int i = 1; i < arr.length; i++) {
            T key = arr[i]; //保存本次要插入的值，以免每次都要交换
            int j = i - 1;
            while (j >= 0) {
                if (key.compareTo(arr[j]) < 0) {
                    arr[j + 1] = arr[j];
                    j--;
                } else {
                    break;
                }
            }
            arr[j + 1] = key;
        }
    }
}
